package com.kobeliu.entity;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Leetcode 18
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 *     0 <= a, b, c, d < n
 *     a、b、c 和 d 互不相同
 *     nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 * 示例 1：
 * 输入：nums = [1,0,-1,0,-2,2], target = 0
 * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 *
 * 示例 2：
 * 输入：nums = [2,2,2,2,2], target = 8
 * 输出：[[2,2,2,2]]
 */
public class Demo_20_No18 {

    public static void main(String[] args) {

        int[] nums = {-2,-1,-1,1,1,2,2};
        System.out.println(fourSum(nums,0));
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {

        //先排序，Arrays自带的排序是归并
        Arrays.sort(nums);

        List<List<Integer>> all = new ArrayList<List<Integer>>(); //装全部的

        //四个指针 头尾 中间两个自由指针
        int len = nums.length;
        if(len < 4){
            return all;
        }
        if(len == 4){
            if(nums[0]+nums[1]+nums[2]+nums[3] == target){
                List<Integer> ns = new ArrayList<Integer>(); //单个数组
                ns.add(nums[0]);
                ns.add(nums[1]);
                ns.add(nums[2]);
                ns.add(nums[3]);
                all.add(ns);
            }
            return all;
        }
        int sum = 0;
        for (int i = 0; i < len-3; i++) {
            //这个与上一个一样直接跳，重复了
            if(i>0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < len-2; j++) {
                //这个与上一个一样直接跳，重复了 这里要注意
                if(j>i+1 && nums[j] == nums[j-1]) continue;
                int L = j+1;
                int R = len-1;
                while(L<R){
                    // i j L R 为四个指针，现在 i j 相当于是固定的，移动L R两个指针
                    sum = nums[i]+nums[j]+nums[L]+nums[R];
                    if(sum < target){
                        L++;
                    }
                    else if(sum>target){
                        R--;
                    }
                    else {
                        List<Integer> ns = new ArrayList<Integer>(); //单个数组
                        ns.add(nums[i]);
                        ns.add(nums[j]);
                        ns.add(nums[L]);
                        ns.add(nums[R]);
                        all.add(ns);
                        //下一个如果一样，就去重
                        while(nums[L] == nums[L+1]) L++;
                        while(nums[R] == nums[R-1]) R--;
                        //不一样的时候，跳到下一个指针
                        L++;
                        R--;
                    }
                }
            }

        }
        return all;
    }
}
